﻿//----------------------------------------------------------------
// Desc: 数据容器
// Edit: ShowLong, http://blog.csdn.net/showlong
//
// Date Created: 2010-12-10
//
// Update Date : 
//
// Copyright (c) Fuel4D (http://www.fuel4d.com), All rights reserved.
//
//----------------------------------------------------------------
#pragma once


//----------------------------------------------------------------
// _BlockObjectCount : 指单块容量，必须是2的幂
//----------------------------------------------------------------
template < typename _Ty, const size_t _BlockObjectCount = 0x1000 >
class FContainer : public IFMemObject
{
    typedef FContainer< _Ty, _BlockObjectCount > _ContainerType;

    struct _TyObject
    {
        BYTE bUsed;             // 当前使用状态
        _Ty pData;              // 数据地址
        size_t bckIndex;        // 自己所处块的索引
        size_t insIndex;        // 自己在块内的索引
    };
    struct _BlockHead
    {
        _TyObject vObject[_BlockObjectCount];// 当前块的头数据首地址
        size_t nUseCount;       // 当前块内使用量
        size_t nFirstLocality;  // 块内首个可见对象索引
        size_t nFirstVisible;   // 首个可用对象索引
        size_t nMyIndex;        // 自己在块内的索引
    };
    enum CONST_CODE
    {
        eIteratorEnd    = 0xcf,
        eMaxBlockIndex  = 0x7fffffff,
    };

    FDECLARE_CLASS(FContainer)

public:
    class iterator
    {
#if FUEL_OS_WINDOWS
        friend class _ContainerType;
#endif

        _TyObject* pObject;
        _ContainerType* pContaner;
        size_t nUsePosition;

        explicit iterator(_ContainerType* ctr, _TyObject* pWhere)
            :pObject(pWhere)
            ,pContaner(ctr)
            ,nUsePosition(0)
        {
        }
    public:
        explicit iterator()
            :pObject(0)
            ,pContaner(0)
            ,nUsePosition(0)
        {
        }
        FINLINE _Ty& operator*()                         { return pObject->pData;                    }
        FINLINE _Ty* operator->()                        { return &pObject->pData;                   }
        FINLINE bool operator==(const iterator& _Right)  { return this->pObject == _Right.pObject;   }
        FINLINE bool operator!=(const iterator& _Right)  { return this->pObject != _Right.pObject;   }
        FINLINE iterator& operator++(int)                { return operator++();                      }
        FINLINE iterator& operator--(int)                { return operator--();                      }
        FINLINE iterator& operator++()
        {
            FASSERT(pContaner, _T("无效的迭代器"));
            if (!pContaner || !pObject || !pContaner->GetNext(*this))
                pObject = (_TyObject*)eIteratorEnd;
            return *this;
        }
        FINLINE iterator& operator--()
        {
            FASSERT(pContaner, _T("无效的迭代器"));
            if (!pContaner || !pObject || !pContaner->GetPrev(*this))
                pObject = (_TyObject*)eIteratorEnd;
            return *this;
        }

    };

    explicit FContainer()
        :nCurObjectCount(0)
        ,nCurBlockCount(0)
        ,pBlockData(0)
        ,nBlockBitOffset(1)
    {
        if (!FIsPower(_BlockObjectCount))
        {
            FASSERT_STR(_T("高速内存池的每块内对象数量必须是2的幂"));
            return;
        }

        // 设置位编移
        while (_BlockObjectCount>>(nBlockBitOffset++))
            ;
        nBlockBitOffset -= 2;

        // 设置循环级别
        switch (_BlockObjectCount)
        {
        case 1: nObjectLoopLevel = 0;   break;
        case 2: nObjectLoopLevel = 1;   break;
        case 4: nObjectLoopLevel = 2;   break;
        case 8: nObjectLoopLevel = 3;   break;
        default:nObjectLoopLevel = 4;
        }
    }
    ~FContainer()
    {
        Release();
    }

    // 分配一个指定ID的对象
    _Ty* Append(size_t ID)
    {
        size_t nBlockIndex = ID>>nBlockBitOffset;
        _BlockHead* pHead = _createBlock(nBlockIndex);
        if (!pHead)
            return 0;

        _TyObject* pObject = pHead->vObject + ID - (nBlockIndex<<nBlockBitOffset);
        if (pObject->bUsed)
            return 0;

        _useObject(pHead, pObject);

        return &pObject->pData;
    }
    // 分配一个对象，自动生成ID
    _Ty* AdvanceNo(size_t& ID)
    {
        for (size_t nBlockIndex = 0; nBlockIndex <= eMaxBlockIndex; ++nBlockIndex)
        {
            _BlockHead* pHead = _createBlock(nBlockIndex);
            if (!pHead || pHead->nUseCount >= _BlockObjectCount)
                continue;

            FASSERT(pHead->nUseCount <= _BlockObjectCount, _T("严重错误"));

            _TyObject* pObject = pHead->vObject + pHead->nFirstVisible;
            for (size_t nIndex = pHead->nFirstVisible; nIndex < _BlockObjectCount; ++nIndex, ++pObject)
            {
                if (pObject->bUsed)
                    continue;

                _useObject(pHead, pObject);

                FASSERT(nBlockIndex == pObject->bckIndex && nIndex == pObject->insIndex, _T("严重错误"));

                ID = (nBlockIndex<<nBlockBitOffset) + nIndex;

                return &pObject->pData;
            }

            FASSERT_STR(_T("严重错误"));
        }

        return 0;
    }
    // 移除一个对象
    bool Remove(size_t ID)
    {
        size_t nBlockIndex = ID>>nBlockBitOffset;
        if (nBlockIndex >= nCurBlockCount || nBlockIndex < 0)
            return false;

        _BlockHead* pHead = pBlockData[nBlockIndex];
        if (!pHead)
            return false;

        _TyObject* pObject = pHead->vObject + ID - (nBlockIndex<<nBlockBitOffset);
        if (!pObject->bUsed)
            return false;

        _unusedObject(pHead, pObject);

        return true;
    }
    // 获取对象
    _Ty* GetData(size_t ID)
    {
        size_t nBlockIndex = ID>>nBlockBitOffset;
        if (nBlockIndex >= nCurBlockCount || nBlockIndex < 0)
            return 0;

        _BlockHead* pHead = pBlockData[nBlockIndex];
        if (!pHead)
            return 0;

        _TyObject* pObject = pHead->vObject + ID - (nBlockIndex<<nBlockBitOffset);
        if (!pObject->bUsed)
            return 0;

        return &pObject->pData;
    }
    // 析构所有对象，并释放内存
    void Release()
    {
        if (!pBlockData)
            return;

        if (nCurObjectCount)
            Clear();

        _BlockHead** pHead = pBlockData;
        for (size_t i = 0; i < nCurBlockCount; ++i, ++pHead)
            FFree(*pHead);
        FFree(pBlockData);

        pBlockData = 0;
        nCurBlockCount = 0;
        nCurObjectCount = 0;
    }
    // 析构所有对象
    void Clear()
    {
        if (nCurObjectCount <= 0)
            return;

        for (size_t nBlockIndex = 0; nCurObjectCount && nBlockIndex < nCurBlockCount; ++nBlockIndex)
        {
            _BlockHead* pHead = pBlockData[nBlockIndex];
            if (!pHead || pHead->nUseCount <= 0)
                continue;

            _TyObject* pObject = pHead->vObject + pHead->nFirstLocality;
            size_t nLoopCount = pHead->nUseCount;
            for (size_t nIndex = pHead->nFirstLocality; nIndex < _BlockObjectCount && nLoopCount; ++nIndex, ++pObject)
            {
                if (!pObject->bUsed)
                    continue;

                _unusedObject(pHead, pObject);
                nLoopCount--;
            }

            FASSERT(!pHead->nUseCount, _T("严重错误"));
        }

        FASSERT(!nCurObjectCount, _T("严重错误"));
    }
    // 获取首
    bool GetFirst(iterator& posi)
    {
        if (nCurObjectCount <= 0)
            return false;

        for (size_t nBlockIndex = 0; nBlockIndex < nCurBlockCount; ++nBlockIndex)
        {
            _BlockHead* pHead = pBlockData[nBlockIndex];
            if (!pHead || pHead->nUseCount <= 0)
                continue;

            _TyObject* pObject = pHead->vObject + pHead->nFirstLocality;
            for (size_t nIndex = pHead->nFirstLocality; nIndex < _BlockObjectCount; ++nIndex, ++pObject)
            {
                if (!pObject->bUsed)
                    continue;

                posi.pObject = pObject;
                posi.pContaner = this;
                posi.nUsePosition = 1;
                return true;
            }
        }

        FASSERT(!nCurObjectCount, _T("严重错误"));

        return false;
    }
    // 获取下一个
    bool GetNext(iterator& posi)
    {
        if (nCurObjectCount <= 0 || !posi.pObject)
            return false;

        size_t noffset = posi.pObject->insIndex + 1;
        for (size_t nBlockIndex = posi.pObject->bckIndex; nBlockIndex < nCurBlockCount; ++nBlockIndex)
        {
            _BlockHead* pHead = pBlockData[nBlockIndex];
            if (!pHead || pHead->nUseCount <= 0)
                continue;

            if (posi.nUsePosition < pHead->nUseCount)
            {
                _TyObject* pObject = pHead->vObject + noffset;
                for (size_t nIndex = noffset; nIndex < _BlockObjectCount; ++nIndex, ++pObject)
                {
                    if (pObject->bUsed)
                    {
                        FASSERT(pObject->bckIndex == nBlockIndex && pObject->insIndex == nIndex, _T("严重错误"));

                        posi.pObject = pObject;
                        posi.pContaner = this;
                        posi.nUsePosition++;
                        return true;
                    }
                }
            }

            noffset = 0;
            posi.nUsePosition = 0;
        }

        return false;
    }
    // 获取上一个
    bool GetPrev(iterator& posi)
    {
        if (nCurObjectCount <= 0 || !posi.pObject)
            return false;

        int noffset = (int)posi.pObject->insIndex - 1;
        for (int nBlockIndex = (int)posi.pObject->bckIndex; nBlockIndex >= 0; --nBlockIndex)
        {
            _BlockHead* pHead = pBlockData[nBlockIndex];
            if (!pHead || pHead->nUseCount <= 0)
                continue;

            posi.nUsePosition = pHead->nUseCount + 1;

            _TyObject* pObject = pHead->vObject + noffset;
            for (int nIndex = noffset; nIndex >= (int)pHead->nFirstLocality; --nIndex, --pObject)
            {
                if (pObject->bUsed)
                {
                    FASSERT(pObject->bckIndex == nBlockIndex && pObject->insIndex == nIndex, _T("严重错误"));

                    posi.pObject = pObject;
                    posi.pContaner = this;
                    posi.nUsePosition--;
                    return true;
                }
            }

            noffset = 0;
        }

        return false;
    }
    FINLINE bool IsUsing(_Ty*& pData)
    {
        if (!pData)
            return false;

        return (FSTRUCT_ADDR(_TyObject, pData))->bUsed != 0;
    }
    FINLINE const _Ty* GetDataByIndex(size_t ID)
    {
        return GetData(ID);
    }
    FINLINE size_t GetCount()
    {
        return nCurObjectCount;
    }
    FINLINE _Ty* operator[](size_t ID)
    {
        return GetData(ID);
    }
    FINLINE iterator begin()
    {
        iterator ret;
        if (GetFirst(ret))
            return ret;

        return end();
    }
    FINLINE iterator end()
    {
        return iterator(this, (_TyObject*)eIteratorEnd);
    }
    FINLINE iterator erase(iterator& itrWhere)
    {
        if (!itrWhere.pObject || itrWhere.pObject == (_TyObject*)eIteratorEnd)
            return end();

        if (!Remove((itrWhere.pObject->bckIndex<<nBlockBitOffset) + itrWhere.pObject->insIndex))
            return end();

        if (nCurObjectCount)
            return ++itrWhere;

        return end();
    }
    FINLINE void reserve(size_t count)
    {
        _createBlock(count>>nBlockBitOffset);
    }

protected:
    size_t nCurObjectCount;     // 当前使用中的对象数
    size_t nCurBlockCount;      // 当前有多少个对象组指针
    _BlockHead** pBlockData;    // 对象组的指针
    size_t nBlockBitOffset;     // 块对象数位偏移
    BYTE nObjectLoopLevel;      // 块对象的循环级别


    FINLINE _BlockHead* _createBlock(size_t block_index)
    {
        FASSERT(block_index <= eMaxBlockIndex, _T("块索引太大"));
        if (block_index > eMaxBlockIndex)
            return 0;

        if (block_index >= nCurBlockCount && nCurBlockCount < eMaxBlockIndex)
        {
            size_t nNewBlockCount = block_index + (block_index>>1) + 1;
            if (nNewBlockCount > eMaxBlockIndex)
                nNewBlockCount = eMaxBlockIndex;
            size_t nNewMemSize = sizeof(_BlockHead*) * nNewBlockCount;
            _BlockHead** pNewBlock = FAlloc(_BlockHead*, nNewMemSize);
            if (pBlockData)
            {
                size_t nCurMemSize = sizeof(_BlockHead*) * nCurBlockCount;
                FMemcpy(pNewBlock, pBlockData, nCurMemSize);
                FMemzero(pNewBlock + nCurBlockCount, nNewMemSize - nCurMemSize);
                FFree(pBlockData);
            }
            else
                FMemzero(pNewBlock, nNewMemSize);
            pBlockData = pNewBlock;
            nCurBlockCount = nNewBlockCount;
        }

        _BlockHead*& pHead = pBlockData[block_index];
        if (!pHead)
        {
            pHead = FAlloc(_BlockHead, 1);
            _createHead(pHead, block_index);
        }

        return pHead;
    }
    FINLINE void _createHead(_BlockHead* pHead, size_t block_index)
    {
        FMemzero(pHead, sizeof(_BlockHead));

        //pHead->nUseCount = 0;
        pHead->nFirstLocality = _BlockObjectCount;
        //pHead->nFirstVisible  = 0;
        pHead->nMyIndex = block_index;

        _TyObject* pNewObject = pHead->vObject;

        switch (nObjectLoopLevel)
        {
        case 0:
            pNewObject->bckIndex = block_index;
            break;
        case 1:
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 1;
            pNewObject->bckIndex = block_index;
            break;
        case 2:
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 1;
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 2;
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 3;
            pNewObject->bckIndex = block_index;
            break;
        case 3:
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 1;
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 2;
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 3;
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 4;
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 5;
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 6;
            pNewObject->bckIndex = block_index;
            (++pNewObject)->insIndex = 7;
            pNewObject->bckIndex = block_index;
            break;
        case 4:
            {
            size_t nCount = _BlockObjectCount>>nObjectLoopLevel;
            for (size_t i = 0; nCount;--nCount)
            {
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
                pNewObject->bckIndex = block_index;
                (pNewObject++)->insIndex = i++;
            }
            }
            break;
        default:
            FASSERT_STR(_T("严重错误"));
        }

    }
    FINLINE void _useObject(_BlockHead* pHead, _TyObject* pObject)
    {
        FASSERT(!pObject->bUsed, _T("对象状态不正确"));

        FNewPT(&pObject->pData, _Ty);

        pObject->bUsed = 1;
        pHead->nUseCount++;
        nCurObjectCount++;

        if (pObject->insIndex < pHead->nFirstLocality)
            pHead->nFirstLocality = pObject->insIndex;

        if (pObject->insIndex == pHead->nFirstVisible)
        {
            _TyObject* pLocal = pHead->vObject + (++pHead->nFirstVisible);
            for (; pHead->nFirstVisible < _BlockObjectCount; ++pHead->nFirstVisible, ++pLocal)
            {
                if (!pLocal->bUsed)
                    break;
            }
        }
    }
    FINLINE void _unusedObject(_BlockHead* pHead, _TyObject* pObject)
    {
        FASSERT(pObject->bUsed, _T("对象状态不正确"));

        pObject->pData.~_Ty();
        pObject->bUsed = 0;
        pHead->nUseCount--;
        nCurObjectCount--;

        if (!pHead->nUseCount)
        {
            pHead->nFirstLocality = _BlockObjectCount;
            pHead->nFirstVisible  = 0;
        }
        else
        {
            if (pObject->insIndex == pHead->nFirstLocality)
            {
                _TyObject* pLocal = pHead->vObject + (++pHead->nFirstLocality);
                for (; pHead->nFirstLocality < _BlockObjectCount; ++pHead->nFirstLocality, ++pLocal)
                {
                    if (pLocal->bUsed)
                        break;
                }
            }

            if (pObject->insIndex < pHead->nFirstVisible)
                pHead->nFirstVisible = pObject->insIndex;
        }
    }
};